package interview;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个整数数组 nums ，请你找出一个具有“最大和”并且”值连续“的子数组（子数组最少包含一个元素），返回其最大和。 说明：”值连续“是指后一个数比前一个数大1； 示例：
 * [1,-3,-2,3,4,5,6,7,9,8,13,15,17,18,19,24,39,41,56,28,14,25,40,2]
 *
 * @author zhangjie
 */
public class SubSumTest {

  public static void main(String[] args) {
    int[] nums = new int[]{1, -3, -2, 3, 4, 5, 6, 7, 9, 8, 13, 15, 17, 18, 19, 24, 39, 41, 56, 28,
        14, 25, 40, 2};
    int sum = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
      int preNum = nums[i];
      for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] - nums[j - 1] != 1) {
          break;
        }
        preNum += nums[j];
      }
      sum = Math.max(sum, preNum);
    }

    System.out.println(sum);

    //单调栈解法
    int sum2 = soluction2(nums);
    System.out.println(sum2);
  }
  public static int soluction2(int[] nums){
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(nums[0]);
    int max = Integer.MIN_VALUE;

    for(int i = 1; i < nums.length; i++){
      int pre = 0;
      while(!stack.isEmpty()&&nums[i]-stack.peek()!=1){
        pre+=stack.poll();
      }
      if(pre!=0){
        max = Math.max(max,pre);
      }
      stack.push(nums[i]);
    }

    int pre = 0;
    while(!stack.isEmpty()){
      pre+=stack.poll();
    }
    max = Math.max(max,pre);

    return max;
  }
}
